#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <sstream>


using namespace std;

// 2512. 奖励最顶尖的 K 名学生
class Solution1
{
public:
    vector<int> topStudents(vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int>& student_id, int k) 
    {
        unordered_set<string> good, bad;
        for(auto& p : positive_feedback) good.insert(p);
        for(auto& n : negative_feedback) bad.insert(n);
        
        unordered_map<int, int> scoreMap(report.size());
        for(int i = 0; i < report.size(); ++i)
        {
            stringstream ss;
            string a;
            ss << report[i];
            while(ss >> a)
            {
                if(good.find(a) != good.end()) scoreMap[student_id[i]] +=3;
                if(bad.find(a) != bad.end()) scoreMap[student_id[i]] -= 1;
            }
        }

        sort(student_id.begin(), student_id.end(), [&](int a, int b){
            if(scoreMap[a] < scoreMap[b])
                return false;
            else if(scoreMap[a] > scoreMap[b])
                return true;
            else
                return a < b;
        });

        return {student_id.begin(), student_id.begin() + k};
    }
};

// 2511. 最多可以摧毁的敌人城堡数目
class Solution2
{
public:
    int captureForts(vector<int>& forts) 
    {
        int ret = 0, pre = -1;
        for(int i = 0; i < forts.size(); ++i)
        {
            if(forts[i] == 1 || forts[i] == -1)
            {
                if(pre >= 0 && forts[i] != forts[pre])
                {
                    ret = max(ret, i - pre - 1);
                }
                pre = i;
            }
        }
        return ret;
    }
};

// 2845. 统计趣味子数组的数目
class Solution3
{
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) 
    {
        unordered_map<int, int> m;
        m[0] = 1;
        long long ret = 0;
        int prev = 0;
        for(int x : nums)
        {
            prev += x % modulo == k;
            ret += m[(prev - k + modulo) % modulo];
            ++m[prev % modulo];
        }
        return ret;
    }
};

// LCR 010. 和为 K 的子数组
class Solution4
{
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int, int> m;
        m[0] = 1;
        int prev = 0, ret = 0;
        for(int x : nums)
        {
            prev += x;
            ret += m[prev - k];
            ++m[prev];
        }
        return ret;
    }
};

// 974. 和可被 K 整除的子数组
class Solution5
{
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        unordered_map<int, int> m;
        m[0] = 1;
        int ret = 0, sum = 0;
        for(int x : nums)
        {
            sum += x;
            int r = (sum % k + k) % k;
            ret += m[r];
            ++m[r];
        }
        return ret;
    }
};

// LCR 011. 连续数组
class Solution6
{
public:
    int findMaxLength(vector<int>& nums) 
    {
        unordered_map<int, int> m;
        m[0] = -1;
        int ret = 0, sum = 0, n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            sum += (nums[i] ? 1 : -1);
            if(m.count(sum))
            {
                int prevIndex = m[sum];
                ret = max(ret, i - prevIndex);
            }
            else
                m[sum] = i;
        }
        return ret;
    }
};

// 2843. 统计对称整数的数目
class Solution7
{
public:
    int countSymmetricIntegers(int low, int high) 
    {
        int ret = 0;
        for(int i = low; i <= high; ++i)
        {
            string s = to_string(i);
            int n = s.size();
            if(n % 2 == 0 && accumulate(s.begin(), s.begin() + n / 2, 0) == accumulate(s.begin() + n / 2, s.end(), 0))
                ++ret;
        }    
        return ret;
    }
};

// 2844. 生成特殊数字的最少操作
class Solution8
{
public:
    int minimumOperations(string num) 
    {
        int n = num.size();
        auto f = [&](const string& s)
        {
            int i = num.rfind(s[1]);
            if(i == string::npos || i == 0) return n;
            i = num.rfind(s[0], i - 1);
            if(i == string::npos) return n;
            return n - i - 2;
        };

        return min({n - (num.find('0') != string::npos), f("00"), f("25"), f("50"), f("75")});
    }
};

// 1277. 统计全为 1 的正方形子矩阵
class Solution9
{
public:
    int countSquares(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        int ret = 0;
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(matrix[i - 1][j - 1] == 0)
                    dp[i][j] = 0;
                else
                    dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                
                ret += dp[i][j];
            }
        }

        return ret;
    }
};